package kibahed.university.effizientealgorithmen.algortihms;

import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Set;

import kibahed.university.effizientealgorithmen.interfaces.AAlgorithm;
import kibahed.university.effizientealgorithmen.interfaces.IEdge;
import kibahed.university.effizientealgorithmen.interfaces.IGraph;
import kibahed.university.effizientealgorithmen.standardclasses.EdgeWithCosts;

public class ExtendedSimpleMatching extends AAlgorithm {

	PriorityQueue<EdgeWithCosts> queue = new PriorityQueue<EdgeWithCosts>();

	PriorityQueue<EdgeWithCosts> oddEdges = new PriorityQueue<EdgeWithCosts>();

	Set<IEdge> minimalSpanningTree = new HashSet<IEdge>();

	int[] parts = null;
	int[] sz = null;
	int[] connectionCount = null;
	Set<Integer> oddNodes = new HashSet<Integer>();

	@SuppressWarnings("unchecked")
	public ExtendedSimpleMatching(IGraph graph) {
		setGraph(graph);
		queue.addAll((Collection<? extends EdgeWithCosts>) graph.getEdges());
		parts = new int[graph.getVertexes().length];
		connectionCount = new int[graph.getVertexes().length];
		initParts();
		sz = new int[graph.getVertexes().length];
	}

	private void initParts() {
		for (int i = 0; i < parts.length; i++) {
			parts[i] = i;
		}
	}

	private void updateParts(int start, int end) {
		int newEnd = parts[end];
		for (int i = 0; i < parts.length; i++) {
			if (parts[i] == newEnd) {
				parts[i] = parts[start];
			}
		}
	}

	@Override
	public void calculate() {
		System.out.println("STARTING KRUSKAL");
		do {
			IEdge e = queue.remove();
			int start = e.getStart();
			int end = e.getEnd();
			if ((parts[start] != parts[end])) {
				minimalSpanningTree.add(e);
				connectionCount[start]++;
				connectionCount[end]++;
				System.out.println(connectionCount[start]);
				updateParts(start, end);

			}

		} while (!queue.isEmpty());

		

		graph.setEdgeTour(minimalSpanningTree
				.toArray(new IEdge[minimalSpanningTree.size()]));

		for (int node = 0; node < graph.getVertexes().length; node++) { // All
																		// odd
																		// nodes
			if (connectionCount[node] % 2 == 1) {
				oddNodes.add(node);
			}
		}

		for (int node : oddNodes) {
			for (IEdge edge : graph.getVertexes()[node].getEdges()) {
				if (oddNodes.contains(edge.getStart())
						&& oddNodes.contains(edge.getEnd())&&!minimalSpanningTree.contains(edge)) {
					oddEdges.add((EdgeWithCosts) edge);
				}
			}
		}

		List<IEdge> newEdges = new LinkedList<IEdge>();
		do {
			EdgeWithCosts edge = oddEdges.remove();
			if (oddNodes.contains(edge.getStart())
					&& oddNodes.contains(edge.getEnd())) {
				oddNodes.remove(edge.getStart());
				oddNodes.remove(edge.getEnd());
				newEdges.add(edge);
			}
		} while (!oddEdges.isEmpty());
		minimalSpanningTree.addAll(newEdges);
		connectionCount = new int[graph.getVertexes().length];
		for (IEdge e : minimalSpanningTree) {
			connectionCount[e.getStart()]++;
			connectionCount[e.getEnd()]++;
		}

		graph.setEdgeTour(minimalSpanningTree
				.toArray(new IEdge[minimalSpanningTree.size()]));
		setResult(minimalSpanningTree
				.toArray(new IEdge[minimalSpanningTree.size()]));
		
		double length = 0;
		for (IEdge e : minimalSpanningTree) {
			length += ((EdgeWithCosts) e).getCost();
		}
		
		addConsoleText("EXTENDED-SIMPLE-MATCHING");
		addConsoleText("Length of tour = "+length);
		graph.addMessages(getConsoleText());
	}

	private IEdge getEdge(int pos1, int pos2) {
		for(IEdge edge:graph.getEdges()){
			if((edge.getStart()==pos1&&edge.getEnd()==pos2)||(edge.getStart()==pos2&&edge.getEnd()==pos1)){
				return edge;
			}
		}
		return null;
	}
}
